package examination_practice01;

public class MaxSonArray {
    //动态规划求最大子段和
    public static int DPMaxArray(int[] arr){
        int n=arr.length;
        int[] dp=new int[n+1];//dp[i]表示以arr[i-1]结尾的最大子段和
        int Sum=Integer.MIN_VALUE;//将Sum设置为最小值
        for (int i=1;i<=n;i++){
            //以arr[i-1]结尾的子序列，如果arr[i-1]小于0，则最大子段和就是arr[i-1]本身
            //如果arr[i-1]大于或等于0，则最大子段和就是结尾元素（arr[i-1]）+前面的子段和(dp[i-1])
            dp[i]=Math.max(arr[i-1],dp[i-1]+arr[i-1]);
            Sum=Math.max(Sum,dp[i]);
        }
        return Sum;
    }
    //暴力枚举求最大子段和
    public static int BFMaxArray(int[] arr){
        int sum=0;
        int n=arr.length;
        for (int i=0;i<n;i++){
            for (int j=i;j<n;j++){
                int currentSum=0;
                for (int k = i; k <= j; k++) {
                    currentSum+=arr[k];
                }
                if (currentSum>sum){
                    sum=currentSum;
                }
            }
        }
        return sum;
    }

    //使用分治法求最大子段和
    public static int DCMaxArray(int[] arr) {
        return divideAndConquer(arr, 0, arr.length - 1);
    }

    /**
     * 分治算法求解最大子数组和
     * @param arr 目标数组
     * @param start 起始位置
     * @param end 结束位置
     * @return 最大子数组和
     */
    private static int divideAndConquer(int[] arr, int start, int end) {
        // 如果起始位置等于结束位置，表示只有一个元素
        if (start == end) {
            // 如果该元素大于0，则返回该元素，否则返回0
            return arr[start] > 0 ? arr[start] : 0;
        }

        // 中间位置
        int mid = (start + end) / 2;

        // 递归求解左半部分的最大子数组和
        int leftMax = divideAndConquer(arr, start, mid);
        // 递归求解右半部分的最大子数组和
        int rightMax = divideAndConquer(arr, mid + 1, end);

        // 计算跨越中间位置的最大子数组和
        int crossingMax = findCrossingMax(arr, start, mid, end);

        // 取左半部分和右半部分的最大子数组和的较大值与跨越中间位置的最大子数组和的较大值作为最终的最大子数组和
        return Math.max(Math.max(leftMax, rightMax), crossingMax);
    }

    /**
     * 计算跨越中间位置的最大子数组和
     * @param arr 目标数组
     * @param start 起始位置
     * @param mid 中间位置
     * @param end 结束位置
     * @return 跨越中间位置的最大子数组和
     */
    private static int findCrossingMax(int[] arr, int start, int mid, int end) {
        // 从中间位置向左遍历，计算包含中间位置左侧的最大子数组和
        //设置为最小值，因为当这半部分的元素全部为负数时，能确保leftSum接收到这部分负数加起来的和
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= start; i--) {
            sum += arr[i];
            leftSum = Math.max(leftSum, sum);
        }

        // 从中间位置向右遍历，计算包含中间位置右侧元素的最大子数组和
        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= end; i++) {
            sum += arr[i];
            rightSum = Math.max(rightSum, sum);
        }

        // 返回包含中间位置的最大子数组和
        return leftSum + rightSum;
    }
    public static void main(String[] args){
        int[] arr=new int[]{1,2,3,4,5,6,-3};//21
        System.out.println("暴力算法的执行结果："+BFMaxArray(arr));
        int[] arr1=new int[]{1,2,3,4,5,6,-3};
        System.out.println("动态规划的执行结果："+DPMaxArray(arr1));
        int[] arr2=new int[]{1,-2,3,-1,5,6,-3};//16
        System.out.println("分治法的执行结果："+DCMaxArray(arr2));
    }
}
